This invention relates to maintaining information regarding operations to be performed, and particularly to using task description blocks to maintain information regarding operations.
Modem, high-capacity data storage systems often utilize a plurality of physical disk drives for redundant storage of data. This arrangement speeds data access as well as protecting against data loss that might result from the failure of any single disk.
There are two common methods of storing redundant data. According to the first or xe2x80x9cmirrorxe2x80x9d method, data is duplicated and stored on two separate areas of the storage system. In a disk array, for example, identical data is stored on two separate disks. This method has the advantages of high performance and high data availability. However, the mirror method is also relatively expensive, effectively doubling the cost of storing data.
In the second or xe2x80x9cparityxe2x80x9d method, a portion of the storage area is used to store redundant data, but the size of the redundant storage area is less than the remaining storage space used to store the original data. For example, in a disk array having six disks, five disks might be used to store data, with the sixth disk being dedicated to storing redundant data, which is referred to as xe2x80x9cparityxe2x80x9d data. The parity data allows reconstruction of the data from one data disk, using the parity data in conjunction with the data from surviving disks. The parity method is advantageous because it is less costly than the mirror method, but it also has lower performance and availability characteristics in comparison to the mirror method.
Aspects of this invention involve storing redundant data according to parity techniques. In conventional disk arrays utilizing parity storage, the space on the storage disks are configured into multiple storage stripes, where each storage stripe extends across the storage disks. Each stripe consists of multiple segments of storage space, where each segment is that portion of the stripe that resides on a single storage disk of the disk array.
FIG. 1 illustrates a conventional disk array 12 having six storage disks 13. In this simplified example, there are five storage stripes extending across the storage disks. FIG. 1 highlights data and storage segments of a single one of these five stripes. Data segments of the indicated stripe are indicated by cross-hatching. The corresponding parity segment of this same stripe is illustrated in solid black. Generally, of the six segments comprising any given stripe, five of the segments are data segments and the sixth segment is a parity segment.
This type of parity storage is referred to as 5+1 parity storage, indicating that there are five data segments for every single parity segment. This scheme is more generally referred to as N+1 grouping, where N is the actual number of data segments in a data stripe.
N+1 redundancy grouping such as illustrated in FIG. 1 protects against the loss of any single physical storage device. If the storage device fails, its data can be reconstructed from the surviving data. The calculations performed to recover the data are straightforward, and are well-known. Generally, a single parity segment P is calculated from data segments D0 through DNxe2x88x921 in accordance with the following equation:
P+x0+x1+x2+xNxe2x88x921
where x0 through xNxe2x88x921 correspond to the data from data segments D0 through DNxe2x88x921. After the loss of any single data segment, its data can be recovered through a straightforward variation of the same equation.
In many systems, however, it is becoming important to protect against the loss of more than a single storage device. Thus, it is becoming necessary to implement N+2 grouping in redundant storage systems.
While N+2 redundancy grouping enhances data protection, it also involves more complex calculationsxe2x80x94both in initially calculating parity segments and in reconstructing any lost data segments.
A general form of the N+2 parity computation is as follows:
P+p0x0+p1x1+p2x2+pNxe2x88x921xNxe2x88x921
Q+q0x0+q1x1+q2x2+qNxe2x88x921xNxe2x88x921
where:
P is the value of a first parity segment;
Q is the value of a second parity segment;
x0 through xNxe2x88x921 are the values of the data segments
p0 through pNxe2x88x921 and q0 through qNxe2x88x921 are constant coefficients that are particular to a given parity scheme.
These equations form a two-equation system that, by the rules of linear algebra, can potentially solve for any two unknowns xa through xb which represent the data from a single stripe of any two failed storage devices. One requirement is that the two sets of coefficients pi and qi be linearly independent. This requirement is met, for example, if p0=1, p1=1, p2=1; etc.; and q0=1, q1=2, q2=3; etc. Other examples are also possible.
The mathematics of N+2 parity are well-known and are not the primary subject of this description. However, it is apparent from the brief description given above that N+2 parity computations are significantly more complex than N+1 parity computations. In actual implementations of N+2 disk arrays, this complexity threatens to limit the data throughput of storage device controllers and, consequently, of the overall disk array.
A co-pending U.S. patent application Ser. No. 09/808,710, entitled xe2x80x9cEfficient Parity Operationsxe2x80x9d, to inventor Michael B. Jacobson, describes a more efficient way to maintain adequate data throughput in spite of the added complexity resulting from N+2 parity calculations, and is hereby incorporated by reference. However, even with the more efficient methods and means described in this co-pending application, data throughput of storage device controllers can still be adversely affected by inefficient memory structures for storing the information necessary to perform the parity calculations. This invention includes methods and apparatus for using task description blocks to maintain information regarding parity (or other) operations and maintain adequate data throughput.
Using task description blocks to maintain information regarding operations is described herein.
In accordance with one aspect of the invention, a task description block queue stores a pointer to each of multiple task description blocks, and each task description block stores information for one operation. The data for an operation is stored in memory. Each task description block stores information necessary for operation logic to perform a single operation, including pointers to the data stored in memory and a pointer to a result location in memory where results of the operation are to be stored by the operation logic. Once all of this information is stored in the task description block, a pointer to the task description block is stored in the task description block queue, allowing the operation logic to perform the operation whenever it desires.
In accordance with another aspect of the invention involving parity operations, a task description block queue stores a pointer to each of multiple task description blocks, and each task description block stores information for one parity operation. The data for a parity operation is stored in memory, as is a plurality of different coefficients that are used for different parity operations. Each task description block stores information used by parity operation logic to perform a single parity operation, including: a type of operation to be performed, a size of the task description block, an optional tag number (for consistency checking), an indication of a response queue into which status results of the operation to be performed are to be stored, pointers to the data stored in memory, a pointer to a subset of the plurality of coefficients, an indication of the number of coefficients in the subset, and a pointer to a result location in memory where results of the parity operation are to be stored by the parity operation logic. Once all of this information is stored in the task description block, a pointer to the task description block is stored in the task description block queue, allowing the parity operation logic to perform the parity operation whenever it desires.